package com.kevin.Code.DP;

/**
 * @author Vinlee Xiao
 * @Classname LongestPalindromicSubsequence
 * @Description Leetcode 516 最长回文子序列 中等难度 动态规划 滚动数组
 * @Date 2021/10/1 20:31
 * @Version 1.0
 */
public class LongestPalindromicSubsequence {


    /**
     * 动态规划代码虽简单，但是思想难以理解
     *
     * @param s
     * @return
     */
    public int longestPalindromeSubseq(String s) {

        int len = s.length();

        if (len == 1) {
            return 1;
        }


        //明确dp数组的含义 dp[i][j]表示 i...j字符串最长回文子序列的长度
        //s.charAt(i)
        int dp[][] = new int[len][len];

        for (int i = len - 1; i >= 0; i--) {
            char s1 = s.charAt(i);
            //边界初始化
            dp[i][i] = 1;
            for (int j = i + 1; j < len; j++) {
                //当两个字符相等时,i+1,j-1
                if (s1 == s.charAt(j)) {

                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }


        return dp[0][len - 1];
    }


    public static void main(String[] args) {
        LongestPalindromicSubsequence longestPalindromicSubsequence = new LongestPalindromicSubsequence();

        int i = longestPalindromicSubsequence.longestPalindromeSubseq("bbbab");
        System.out.println(i);
    }
}
